package run.siyuan.jdk.算法_4版.课后练习;

import edu.princeton.cs.algs4.ST;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import org.junit.jupiter.api.Test;

import java.text.NumberFormat;
import java.util.Arrays;

/**
 * @className: 第一章
 * @Description: TODO
 * @author: siyuan
 * @date: 2022/11/29 16:11
 */
public class Chapter1 {

    /**
     * (0+15)/2
     * 2.0e-6*100000000.1
     * true && false || true && true
     */
    @Test
    public void practice1() {
        // 7
        System.out.println((0 + 15) / 2);
        /*
         * "2e-6"是一种表达一个数的方式——科学计数法，"e"是代表10，"+"代表乘（"-"是代表除）
         * "+" 或 "-" 后面的数字代表 "e" 的次方数，最后再把 "e" 前面的数乘于e的次方
         * 2e-6 = 2 * (1/10^6) = 2 * 0.000001 = 0.000002
         *
         * 200.000002
         */
        System.out.println(2.0e-6 * 100000000.1);
        /**
         * "&&" 优先级高于 "||"
         * "&&" 是短路与，为 true 之后不往后进行
         */
        System.out.println(true && false || true && true);
    }


    /**
     * (1+2.236) /2
     * 1+2+3+4.0
     * 4.1>=4
     * 1+2+"3"
     */
    @Test
    public void practice2() {
        // 1.618 double
        Object v = (1 + 2.236) / 2;
        System.out.println(v + " " + v.getClass().getSimpleName());
        // 10.0 double
        v = 1 + 2 + 3 + 4.0;
        System.out.println(v + " " + v.getClass().getSimpleName());
        // true boolean
        v = 4.1 >= 4;
        System.out.println(v + " " + v.getClass().getSimpleName());
        // "33" String
        v = 1 + 2 + "3";
        System.out.println(v + " " + v.getClass().getSimpleName());
    }

    /**
     * 从命令行得到三个整数，如果他们都相等泽打印equal，如果他们不相等则打印 not equal
     */
    @Test
    public void practice3() {
        System.out.println("请输入三个整数：");
        int a = StdIn.readInt();
        int b = StdIn.readInt();
        int c = StdIn.readInt();
        System.out.println(a == b && b == c ? "equal" : "not equal");
    }

    /**
     * 编写一段程序，如果double 类型的变量x 和y 都严格位于0 和1 之间则打印true，否则打印
     */
    @Test
    public void practice5() {
        System.out.println("请输入x,y 两个数：");
        double x = StdIn.readDouble();
        double y = StdIn.readDouble();
        boolean result = (x >= 0d && x <= 1d) && (y >= 0d && y <= 1d);
        System.out.println(result);
    }


    @Test
    public void practice6() {
        int f = 0;
        int g = 1;
        for (int i = 0; i <= 15; i++) {
            StdOut.println(f); // 0,1,1,2,3,5,8,13,21,34,55,89,1444,233,377,610
            f = f + g; // 1,1,2,3,5,8,13,21,34,55,89,1444,233,377,610
            g = f - g; // 0,1,1,2,3,5,8,13,21,33,54,87,141,228,369
        }
    }

    @Test
    public void practice7_a() {
        // a
        double t = 9.0;
        // .001 = 0.001
        while (Math.abs(t - 9.0 / t) > .001) {
            t = (9.0 / t + t) / 2.0; // 5.0,3.0
        }
        StdOut.printf("%.5f\n", t);//3.0
    }

    @Test
    public void practice7_b() {
        // b 等列数组：n(n+1)/2
        int sum = 0;
        for (int i = 1; i < 1000; i++) {
            for (int j = 0; j < i; j++) {
                sum++;
            }
        }
        StdOut.println(sum); // 999*(999+1)/2 = 499500
    }

    @Test
    public void practice7_c() {
        // c
        int sum = 0;
        for (int i = 1; i < 1000; i *= 2) // 等比数列 1*2^(n-1) > 1000；n = 10
            for (int j = 0; j < 1000; j++)
                sum++;
        StdOut.println(sum); // 10 * 1000 = 10000
        // 扩展
        sum = 0;
        for (int i = 1; i < 5000; i *= 2) // 等比数列 1*2^(n-1) > 5000；n = 13
            for (int j = 0; j < 1000; j++)
                sum++;
        StdOut.println(sum); // 13 * 1000 = 10000

    }

    @Test
    public void practice8() {
        System.out.println('b'); // b
        System.out.println('b' + 'c'); // 197
        System.out.println((char) ('a' + 4)); // e
    }

    /**
     * 编写一段代码，将一个正整数N 用二进制表示并转换为一个String 类型的值s。
     */
    @Test
    public void practice9() {
        System.out.println("请输入一个整数：");
        int N = StdIn.readInt();
        System.out.println(Integer.toBinaryString(N));
        String s = "";
        for (int i = N; i > 0; i /= 2) {
            s = i % 2 + s;
        }
        System.out.println(s);
    }

    /**
     * 编写一段代码，打印出一个二维布尔数组的内容。其中，使用* 表示真，空格表示假。打印出行号和列号。
     */
    @Test
    public void practice11() {
        int row = 10;
        int column = 10;
        boolean[][] arr = new boolean[row][column];

        for (int i = 0; i < row; i++) {
            // 打印行号
            if (i > 0) {
                StdOut.print(i + 1 + " ");
            }
            // 打印列号
            if (i == 0) {
                for (int k = 0; k < column; k++) {
                    StdOut.print("  " + (k + 1));
                }
                StdOut.println();
                StdOut.print(i + 1 + " ");
            }
            for (int j = 0; j < column; j++) {
                arr[i][j] = StdRandom.bernoulli();
                boolean b = arr[i][j];
                if (b) {
                    StdOut.print("*  ");
                } else {
                    StdOut.print("   ");
                }
            }
            StdOut.println();
        }
    }

    @Test
    public void practice12() {
        int[] a = new int[10];
        for (int i = 0; i < 10; i++) {
            a[i] = 9 - i; // 9,8,7,6,5,4,3,2,1,0
        }
        for (int i = 0; i < 10; i++) {
            a[i] = a[a[i]]; // 0,1,2,3,4,4,3,2,1,0
        }
        for (int i = 0; i < 10; i++) {
            System.out.print(i); // 0,1,2,3,4,5,6,7,8,9
        }
        StdOut.println();
        for (int i = 0; i < 10; i++) {
            System.out.print(a[i]); // 0,1,2,3,4,4,3,2,1,0
        }
    }

    /**
     *
     */
    @Test
    public void practice13() {
        int row = 5;
        int column = 5;
        // 二维数组赋值
        Integer[][] arr = new Integer[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                arr[i][j] = StdRandom.uniformInt(10);
                StdOut.print(arr[i][j] + " ");
            }
            StdOut.println();
        }
        StdOut.println("============");
        for (int i = 0; i < row; i++) {
            for (int j = i; j < column; j++) {
                // 行列交换
                int tem = arr[i][j];
                arr[i][j] = arr[j][i];
                arr[j][i] = tem;
            }
        }
        // 二维数组打印
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                StdOut.print(arr[i][j] + " ");
            }
            StdOut.println();
        }
    }

    /**
     * 编写一个静态方法lg()，接受一个整型参数N，返回不大于log2N 的最大整数。不要使用Math 库。
     */
    @Test
    public void practice14() {
        System.out.println(lg(2));
        System.out.println(lg(4));
        System.out.println(lg(6));
        System.out.println(lg(8));
    }

    public int lg(Integer num) {
        int lgNum = 0;
        if (num < 2) {
            return lgNum;
        }
        lgNum++;
        while (true) {
            num = num / 2;
            if (num >= 2) {
                lgNum++;
            } else {
                break;
            }
        }
        return lgNum;
    }

    /**
     * 编写一个静态方法histogram()，接受一个整型数组a[] 和一个整数M 为参数并返回一个大小为M的数组，其中第i个元素的值为整数i在参数数组中出现的次数。如果a[]中的值均在0到M-1之间，返回数组中所有元素之和应该和a.length 相等。
     */
    @Test
    public void practice15() {
        int[] a = {1, 2, 3, 2};
        int[] newArrA = histogram(a, 5);
        StdOut.println(Arrays.toString(newArrA));

    }

    /**
     * 1. 统计元素出现的次数，很好的利用了int 默认值0
     * 2. 如果a[]中的值均在0到M-1之间，返回数组中所有元素之和应该和a.length 相等。(未实现)
     *
     * @param a
     * @param M
     * @return
     */
    public int[] histogram(int[] a, int M) {
        int[] Marr = new int[M];
        for (int i = 0; i < a.length; i++) {
            int var = a[i];
            Marr[var]++;
        }
        return Marr;
    }

    @Test
    public void practice16() {
        StdOut.println(exR1(6));

    }

    /**
     * 0
     * 1 11
     * 2 22
     * 3 3113
     * 4 114224
     * 5 22531135
     * 6 311361142246
     *
     * @param n
     * @return
     */
    private static String exR1(int n) {
        if (n <= 0) {
            return "";
        }
        return exR1(n - 3) + n + exR1(n - 2) + n;
    }


    @Test
    public void practice18() {
        StdOut.println(mystery(2, 25));
        StdOut.println(mystery(3, 11));

        StdOut.println(mysteryMul(2, 25));
        StdOut.println(mysteryMul(3, 11));

    }

    /**
     * 1 % 2 = 1
     *
     * @param a
     * @param b
     * @return
     */
    public static int mystery(int a, int b) {
        if (b == 0) {
            return 0;
        }
        if (b % 2 == 0) {
            return mystery(a + a, b / 2);
        }
        return mystery(a + a, b / 2) + a;
    }

    /**
     * 1 % 2 = 1
     *
     * @param c
     * @param d
     * @return
     */
    public static int mysteryMul(int c, int d) {
        if (d == 0) {
            return 0;
        }
        if (d % 2 == 0) {
            return mysteryMul(c * c, d / 2);
        }
        return mysteryMul(c * c, d / 2) * c;
    }

    @Test
    public void practice19() {
        int row = 50;
        Long[] arr = new Long[row];
        for (int N = 0; N < row; N++) {
            StdOut.println(N + " " + F(N, arr));
        }

    }

    /**
     * 斐波那契数列 又称 黄金分割数列 (0,1,1,2,3,5,8...)
     * F(N) = F(N-1) - F(N-2)
     *
     * @param N
     * @return
     */
    public long F(int N) {
        if (N == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
        return F(N - 1) + F(N - 2);
    }

    /**
     * 斐波那契数列 又称 黄金分割数列 (0,1,1,2,3,5,8...)
     * F(N) = F(N-1) - F(N-2)
     *
     * @param N
     * @return
     */
    public Long F(int N, Long[] arr) {
        Long num = null;
        if (N == 0) {
            num = 0L;
        } else if (N == 1) {
            num = 1L;
        } else {
            num = arr[N - 1] + arr[N - 2];
        }
        arr[N] = num;
        return arr[N];
    }

    @Test
    public void practice20() {
        System.out.println(ln(4));

    }

    public double ln(int num) {
        if (num == 1) {
            return 0;
        }
        return Math.log(num) + ln(num - 1);
    }

    @Test
    public void practice21() {
        System.out.println("请求输入：");
        NumberFormat format = NumberFormat.getInstance();
        format.setMaximumFractionDigits(2);
        while (true) {
            String s1 = StdIn.readLine();
            if (s1 == null || s1.equals("")) {
                break;
            }
            String[] stu = s1.split(" ");

            if (stu[0].equals("return")) {
                break;
            }
            double mechage = Double.parseDouble(stu[1]) / Double.parseDouble(stu[2]);

            StdOut.printf("%s : %s / %s = %s", stu[0], stu[1], stu[2], format.format(mechage));
            StdOut.println();
        }
    }


    @Test
    public void practice22() {
        StdOut.println(binarySearch(11, new int[]{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}));
    }

    public int binarySearch(int key, int[] a) {
        return rank(key, a, 0, a.length - 1, 0);
    }

    /**
     * 二分查找法
     *
     * @param key   目标数
     * @param a     源数组
     * @param lo    开始索引
     * @param hi    结束索引
     * @param depth 循环次数
     * @return 返回目标位置
     */
    public int rank(int key, int[] a, int lo, int hi, int depth) { //如果key存在于a[]中，它的索引不会小于lo且不会大于hi
        depth++;
        StdOut.printf("lo:%s,li:%s,depth:%s \n", lo, hi, depth);
        if (lo > hi) {
            return -1;
        }
        int mid = lo + (hi - lo) / 2;
        if (key < a[mid]) {
            return rank(key, a, lo, mid - 1, depth);
        } else if (key > a[mid]) {
            return rank(key, a, mid + 1, hi, depth);
        } else {
            return mid;
        }
    }


    @Test
    public void practice23() {
        String operation = "-";
         binarySearch(11, new int[]{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, operation);
    }

    public int binarySearch(int key, int[] a, String operation) {
        return rank(key, a, 0, a.length - 1, operation);
    }

    /**
     * 二分查找法
     *
     * @param key       目标数
     * @param a         源数组
     * @param lo        开始索引
     * @param hi        结束索引
     * @param operation +\- 符号
     * @return 返回目标位置
     */
    public int rank(int key, int[] a, int lo, int hi, String operation) { //如果key存在于a[]中，它的索引不会小于lo且不会大于hi
        if (lo > hi) {
            return -1;
        }
        int mid = lo + (hi - lo) / 2;
        if (key < a[mid]) {
            hi = mid - 1;
        } else if (key > a[mid]) {
            lo = mid + 1;
        } else {
            if ("+".equals(operation)){
                for (int i = 0; i < a.length; i++) {
                    if (i != mid){
                        StdOut.print(a[i] + " ");
                    }
                }
            }else {
                StdOut.print(a[mid]+ " ");
            }
            return mid;
        }
        return rank(key, a, lo, hi, operation);
    }


    /**
     * 给出使用欧几里德算法计算105 和24 的最大公约数的过程中得到的一系列p 和q 的值。扩展该算法中的代码得到一个程序Euclid，从命令行接受两个参数，
     * 计算它们的最大公约数并打印出每次调用递归方法时的两个参数。使用你的程序计算1 111 111 和1 234 567 的最大公约数。
     */
    @Test
    public void practice24() {
        StdOut.println(gcd(105,24));
        StdOut.println(gcd(1,111));
        StdOut.println(gcd(111,1));
        StdOut.println(gcd(234,567));
        StdOut.println(gcd(1997,615));
    }

    /**
     * 欧几里得算法计算最大公寓数
     *
     * @param divisor 除数
     * @param dividend 被除数
     * @return
     */
    public int gcd(int divisor,int dividend){
        int remainder = divisor % dividend;
        if (remainder == 0){
            return dividend;
        }
        if (dividend <= 0){
            return -1;
        }
        return gcd(dividend,remainder);
    }

    /**
     *
     */
    @Test
    public void practice26() {
        int a = 3, b = 1, c = 2, t;

        if (a > b) { t = a; a = b; b = t; }
        if (a > c) { t = a; a = c; c = t; }
        if (b > c) { t = b; b = c; c = t; }
        StdOut.printf("a=%s,b=%s,c=%s", a, b, c);

    }






}















